#ifndef _contest_phi_h_
#define _contest_phi_h_

#include<stdint.h>

namespace contest
{
/**
 * Number of relative primes to n.
 * @param n: The number to calculate. 
 * @return: The number of relative primes. 
 **/
uint32_t phi(uint32_t n)
{
    uint32_t result = 1;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0)
        {
            uint32_t pow = 1;
            while (n % i == 0)
            {
                pow *= i;
                n /= i;
            }
            result *= (pow - pow/i);
        }
    if (n > 1)
        result *= (n - 1);
    return result;
}

void test_phi()
{
    assert(phi(1) == 1);
    assert(phi(2) == 1);
    assert(phi(3) == 2);
    assert(phi(4) == 2);
    assert(phi(5) == 4);
    assert(phi(6) == 2);
}
}

#endif
